\chapter{Conceitos e Definições}\label{cap2}

Neste capítulo, é apresentada uma revisão dos principais conceitos que serão úteis no decorrer da dissertação. Os conceitos sobre geometria computacional são apresentados na Seção \ref{Geometria computacional}. As técnicas de geração de malha, na Seção \ref{Geração de Malha}. Alguns conceitos de Computação de Alto Desempenho, bem como estratégias para administrar tarefas em paralelo, na Seção \ref{Computação de alto desempenho}. Por fim, algumas estruturas de dados que serão utilizadas nesse trabalho são apresentadas, na Seção \ref{Estrutura de dados}.


\section{Geometria Computacional}\label{Geometria computacional}

A geometria computacional é a área da computação que estuda soluções e estruturas de dados para problemas geométricos. O seu enfoque é buscar soluções sob o ponto de vista da análise de complexidade de algoritmos. Entre os problemas estudados estão a construção de fechos convexos, triangulações, ordenação de pontos espaciais, interseções de retas/planos, malhas e outros mais.

\subsection{Fecho Convexo}

O fecho convexo de um conjunto finito de pontos é o menor conjunto convexo que contém tais pontos. Segundo \cite{bib:Carvalho91} um conjunto $K$ do $\Re^{n}$, sendo $n$ um inteiro não negativo, é convexo se quaisquer que sejam  $x \in K$, $y \in K$ e $0 \leq \lambda \leq 1$, $\lambda \in \Re$ , tem-se $\lambda x + (1-\lambda)y \in K $. Ou seja, todas as combinações convexas dos elementos de $K$ pertencem a $K$. Um ponto $p$ é dito ser combinação convexa dos pontos $p_{i} \in K$  se $p = \displaystyle\sum_{i=1}^{|K|} p_{i}\lambda_i $, sendo $ \displaystyle\sum_{i=1}^{|K|} \lambda_i = 1 $.

Um ponto $w \in K$ é um ponto extremo de $K$ se não pode ser conectado a um elemento de $K$ por um segmento de reta aberto pertencente a $K$. O fecho convexo de um conjunto finito $C$ de pontos no $\Re^{n}$, sendo $n$ um inteiro não negativo, é o conjunto de todas as combinações convexas de elementos de $C$. Em outras palavras pode-se dizer que o fecho convexo é um conjunto finito de pontos com menor área geométrica que engloba todos os pontos do conjunto (Figura \ref{fig:fecho convexo}).

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.5\textwidth]{fig/fecho_convexo.png}
     \caption{Conjunto de pontos e o seu fecho convexo.} 
     \label{fig:fecho convexo}
 \end{figure}

\subsection{Ponto de Steiner}

No triângulo ABC, sejam:
\begin{itemize}
  \item A’ o simétrico de A em relação a G
  \item B’ o simétrico de B em relação a G
  \item C’ o simétrico de C em relação a G;
\end{itemize}

As três circunferências definidas pelos conjuntos de ternos de pontos AB’C’, BA’C’, CA’B’ intersectam-se num ponto do circuncírculo - ponto de Steiner. A cada uma das três circunferências dá-se o nome de “círculo de Steiner”, como mostra a figura \ref{fig:steiner}.

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.8\textwidth]{fig/steiner.png}
     \caption{Ponto de Steiner para um triângulo ABC.} 
     \label{fig:steiner}
 \end{figure}

\subsection{Triangulação e Malha}

Triangulações são muitas vezes chamadas de malhas ou usadas como malhas, como no caso do método dos elementos finitos (MEF), já que malha é uma união de elementos, que podem ser triângulos, por exemplo. Pode-se definir uma malha $M$ de uma maneira genérica como:

\begin{itemize}
 \item $\varOmega = \bigcup\limits_{k \in M} k $, onde $\varOmega$ é um domínio finito limitado,
 \item O interior de cada elemento $k$ em $M$ é não vazio,
 \item A interseção do interior de dois elementos de $M$ é vazia.
\end{itemize}

Uma triangulação também é uma malha, mas nem toda malha é uma triangulação. Neste trabalho quando for mencionado malha, será sempre a malha que respeita as mesmas propriedades de uma triangulação. A definição de triangulação segundo \cite{bib:Triangulations_applications} diz que:

\begin{itemize}
  \item Nenhum triangulo pertencente à triangulação pode ter pontos colineares.
  \item A interseção do interior de quaisquer dois triângulos pertencentes à triangulação é vazia.
  \item As bordas de 2 triângulos quaisquer só podem fazer interseção com vértices ou arestas.
  \item A união de todos os triângulos da triangulação é igual ao domínio.  
  \item O domínio deve ser conectado.
  \item Não deve existir buracos na triangulação, a menos que eles sejam definidos como entrada.
  \item Se um triângulo está na borda da triangulação então ele faz interseção por aresta no máximo dois triângulos.
\end{itemize}


Existem malhas de diferentes geometrias e dimensões. Caso a topologia de elementos e vértices da malha siga alguma regra simples de indexação, essa malha será definida como estruturada, caso contrário, ela é definida como não-estruturada. Nas malhas estruturadas o conhecimento dos vizinhos de cada elemento não depende do armazenamento ou existência desta informação. Já nas não-estruturadas, para se ter conhecimento dos vizinhos, é necessário armazenar ou calcular estas informações. Existem ainda as malhas mistas, que combinam malhas estruturadas e não-estruturadas (Figura \ref{fig:est_e_n_est}).

As malhas também podem ser classificadas de acordo com a geometria dos seus elementos, já que não são necessariamente formadas somente de triângulos.. Para malhas bidimensionais, por exemplo, elas podem ser de elementos triangulares ou quadrilaterais, por exemplo, como mostra a Figura \ref{fig:est_e_n_est}.

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.5\textwidth]{fig/est_e_n_est.png}
     \caption{Exemplo de malha quadrilateral estruturada e não-estruturada triangular.} 
     \label{fig:est_e_n_est}
 \end{figure}
 
Para muitas aplicações, a qualidade dos elementos da malha é muito importante. Para classificar um elemento de uma malha triangular como bom ou ruim pode-se utilizar, dentre outras, uma métrica que é definida como $ \alpha = 2R_i / R_c $, onde $R_i$ e $R_c$ são os raios dos círculos inscrito e circunscrito, respectivamente. 
 
Esta métrica $\alpha$ tem valor $1,0$ para um triângulo equilátero. Quanto pior a qualidade do elemento, mais próximo de $0,0$ é o valor de $\alpha$. Pode-se dizer que os elementos com $\alpha \leq 0,1$ são de péssima qualidade e que os elementos com $\alpha \geq 0,7$ são de boa qualidade, como mostra a Figura \ref{fig:qualidade_elemento}.

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.5\textwidth]{fig/qualidade_elemento.png}
     \caption{Exemplo de um elemento triangular de boa qualidade (esquerda) e dois de péssima qualidade (direita).} 
     \label{fig:qualidade_elemento}
 \end{figure}

\section{Geração de Malha}\label{Geração de Malha}

Nesta seção, são apresentadas as técnicas de geração de malhas triangulares mais conhecidas atualmente. Existem diversos algoritmos para geração de malhas, porém eles podem ser enquadrados uma das categorias a seguir:

\begin{itemize}
  \item Avanço de fronteira, técnica em que a malha é gerada a partir da borda da região;

  \item Delaunay, técnica em que a malha é gerada procurando-se maximizar o menor ângulo dos triângulos gerados para um dado conjunto de pontos;

  \item Arbitrária, técnica em que a malha é gerada de maneira diferente das anteriores.
\end{itemize}

\subsection{Avanço de Fronteira}

Este é um dos métodos mais populares de geração de malhas e consiste em criar os elementos no interior do domínio progressivamente a partir de um contorno, especificando a região a ser preenchida (Figura~\ref{fig:AF}a). Este contorno é chamado de fronteira inicial ou borda. Os elementos são gerados a partir dessa fronteira dada como entrada. Uma fronteira bidimensional é formada por um conjunto de arestas.

À medida que o algoritmo progride, a fronteira avança em direção ao interior, sempre removendo ou adicionando elementos de fronteira até que todo o domínio seja preenchido. O algoritmo chega ao fim quando não há mais fronteira, ou seja, o domínio foi totalmente triangularizado. 

Há casos em que o algoritmo não consegue mais gerar elementos para uma determinada fronteira, isso indica que o algoritmo falhou. O caso de falha ocorre quando todos os possíveis elementos a serem criados se sobrepõem a um elemento já existente. Por isso, é importante verificar se elementos se interceptam. Os casos de falha geralmente acontecem em modelos tridimensionais. Entretanto, já existem técnicas para contornar esses problemas e gerar malhas em modelos que falhariam.

Para gerar os novos triângulos no interior do domínio, é necessário criar novos pontos que não pertencem aos dados de entrada. Em geral, são utilizados os pontos de Steiner para isso \cite{bib:Ruppert99}.

Um algoritmo de avanço de fronteira procede da seguinte maneira no caso 2D (Figura~\ref{fig:AF}):
 
 \begin{enumerate}
\item{ Selecione uma aresta da fronteira, a aresta base (fig.~\ref{fig:AF}b);}
\item{ Encontre um ponto ideal para a formação de um novo triângulo com a aresta base (fig.~\ref{fig:AF}c);}
\item{ Crie uma região de busca em torno desse ponto ideal (fig.~\ref{fig:AF}d);}
\item{ Selecione o ponto dentro dessa região de busca cujo triângulo (entre esse ponto e a aresta base) seja válido e seja o de melhor qualidade, que pode ser um novo ponto ou um ponto já pertencente à malha;}
\item{ Forme o novo triângulo com o ponto selecionado e adicione-o à malha (fig.~\ref{fig:AF}e);}
\item{ Atualize a fronteira, inserindo as arestas que foram criadas e removendo as arestas que já existiam;}
\item{ Se existir aresta na fronteira, volte para o passo 1.}
\end{enumerate}

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=1\textwidth]{fig/AF.jpg}
     \caption{Avanço de fronteira \cite{bib:Freitas10}.} 
     \label{fig:AF}
 \end{figure}

Pelo fato da fronteira ser sempre respeitada, os algoritmos de avanço de fronteira têm facilidade em tratar regiões descontínuas, ou por conterem buracos, ou por serem regiões separadas. Como os elementos mais próximos da borda são gerados primeiro, em geral, eles têm uma boa qualidade. A boa qualidade da malha gerada provê estabilidade e precisão à aplicação de métodos numéricos (como os métodos dos elementos finitos).

Porém, nem sempre todos os elementos gerados têm boa qualidade. Ao contrário dos elementos mais próximos da borda, os elementos mais internos à malha nem sempre têm boa qualidade devido à região tornar-se menor à medida que a fronteira avança. Geralmente uma técnica de suavização ou otimização é aplicada na malha resultante do algoritmo para tratar esses casos.

\subsection{Delaunay}

Esta é uma técnica bastante conhecida na área de geração de malhas, cujo nome é uma homenagem ao matemático russo Boris Delaunay. A entrada para esse problema é um conjunto de pontos e, geralmente, não são utilizados os pontos de Steiner para formar os triângulos.

O critério de Delaunay para a formação dos triângulos é que não exista nenhum outro ponto dentro do círculo que passa pelos três pontos desse triângulo (seu circuncírculo), critério este também chamado de "esfera vazia" (o circuncírculo desse triângulo, Figura~\ref{fig:criterio_delaunay}). O critério de Delaunay em si não se constitui num método de geração de malhas, mas é uma forma de saber onde os pontos devem estar localizados no espaço.

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.65\textwidth]{fig/criterio_delaunay.jpg}
     \caption{a) Critério de Delaunay falhando para os dois triângulos. b) Triangulação válida respeitando o critério de Delaunay.} 
     \label{fig:criterio_delaunay}
 \end{figure}

A malha gerada por Delaunay visa maximizar os ângulos internos dos triângulos gerados, ou seja, dada uma aresta da triangulação de Delaunay, o ponto que forma o maior ângulo com essa aresta é o ponto que formará um triângulo de Delaunay com ela.

Existem algumas variações de algoritmos de Delaunay. Em uma delas, encontra-se uma aresta que faz parte da triangulação que é, em geral, uma aresta pertencente ao fecho convexo. A partir dela, é encontrado o ponto que formará um triângulo de Delaunay. Assim, com as novas arestas, encontram-se novos triângulos, em um algoritmo parecido com o de avanço de fronteira. Uma outra variação é feita a partir de inserção de pontos. A entrada é uma malha triangular não necessariamente de Delaunay e se modifica essa malha (de apenas um subconjunto de pontos da entrada) pré-existente (Figura~\ref{fig:triangulacao_insercao}).

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=1\textwidth]{fig/triangulacao_insercao.jpg}
     \caption{Triangulação por inserção de pontos \cite{bib:Freitas10}.} 
     \label{fig:triangulacao_insercao}
 \end{figure}

 Dependendo da disposição dos pontos da entrada, a triangulação final pode não ter boa qualidade, principalmente em regiões críticas, próximas à borda, gerando instabilidade em métodos numéricos. Uma alternativa para melhorar essa malha é fazer refinamentos e otimizações, que fazem uso de pontos de Steiner.

\subsection{Arbitrária}

As técnicas de geração de malha arbitrárias são aquelas que não se enquadram nem como Avanço de Fronteira e nem como Delaunay. As malhas são geradas em geral por algoritmos de varredura ou algum outro método.

Outro uso que essas malhas possuem é nas demonstrações de teoremas. O problema de ordenação de pontos pode ser reduzido ao problema de geração de malhas bidimensionais \cite{bib:Carvalho91}. Prova-se por redução que pode ser gerada uma malha triangular a partir do fecho convexo de um conjunto de pontos em duas dimensões numa complexidade na ordem de $O (n \log n)$.

\section{Geração de Malha em Paralelo}\label{Geração de Malha em Paralelo}

Na geração em paralelo é necessário dividir a entrada para realizar o processamento em paralelo das diversas partes. Existem duas formas de decompor o domínio. Na primeira forma, uma malha grosseira da região é rapidamente gerada, sequencialmente, e dividida entre os processadores. Essa forma, chamada de decomposição discreta do domínio, envolve ainda o problema de particionamento da malha. A segunda forma de decompor o domínio envolve dividir a região a partir de funções, segmentos, eixos inerciais, ou estruturas auxiliares, por isso chamada de decomposição contínua do domínio. Cada subdomínio é enviado a um processador, onde a malha será gerada.

Uma malha de interface é um conjunto de segmentos ou triângulos para o caso bidimensional ou, no caso tridimensional, um conjunto de triângulos ou tetraedros. Essa malha de interface faz a conexão entre duas partições vizinhas e faz o papel de uma nova fronteira. A forma que ela é criada vai depender da técnica que está sendo utilizada para particionar o domínio.

O particionamento contínuo pode ainda, ser subdividido em duas categorias, dependendo da forma como é gerada a malha entre os subdomínios, chamada de malha de interface. Se essa malha for gerada antes da malha interna ao subdomínio, essa abordagem é chamada de \textit{a priori}. Caso ela seja gerada depois, é chamada de \textit{a posteriori}. A geração da malha de interface \textit{a posteriori} geralmente requer sincronização entre processos.

\section{Computação de Alto Desempenho}\label{Computação de alto desempenho}

Computação de Alto Desempenho ou HPC (do inglês \textit{High-performance computing}) se refere ao uso de \textit{clusters} ou supercomputadores em tarefas que requerem grandes recursos de computação. O uso eficiente desses recursos é o principal foco de estudo nessa área. \textit{Cluster} é um conjunto de computadores de alto desempenho interconectados por uma rede local que trabalham em conjunto como um único recurso de processamento.

\subsection{Modelos de Arquiteturas}

Em programas que executam sequencialmente não existe a preocupação que uma dada posição de memória seja alterada no mesmo tempo que ela esteja sendo lida. Em computação paralela há essa preocupação e existem várias técnicas para manter a ordem de leitura e escrita na memória. Basicamente há dois tipos de arquiteturas (Figura \ref{fig:arquiteturas}):

  \begin{itemize}
    \item Memória Compartilhada

    Engloba basicamente os sistemas UMA (Uniform Memory Acess), ou seja, o acesso à memória é feito de forma uniforme através de endereçamento direto. Assim, todos os processadores de um computador compartilham um mesmo espaço de memória e para isso deve haver um controle na leitura e escrita na memória.

    \item Memória Distribuída
    
    Cada um dos processadores têm acesso a um espaço único de endereçamento de memória privada. Cada módulo da memória pode ser acessado diretamente por apenas um dos processadores. A comunicação entre os processos ocorre através de troca de mensagens.   
  \end{itemize}

   \begin{figure}[htbp]
     \centering
     \includegraphics[width=1.0\textwidth]{fig/arquiteturas.png}
     \caption{Estratégia de balanceamento não-centralizado onde todos os nós podem se comunicar entre si. Memória compartilhada à esquerda e memória distribuída à direita.} 
     \label{fig:arquiteturas}
 \end{figure}

\subsection{Balanceamento de Carga}\label{Balanceamento de carga}

Uma aplicação que executa em paralelo cria várias novas tarefas que devem ser distribuídas entre os processadores existentes. Quando a quantidade de tarefas se torna maior que a quantidade de processadores disponíveis, torna-se necessário um balanceamento de carga, ou seja,  distribuir o processamento entre os processadores de modo a obter a maior velocidade possível de execução. O principal objetivo é manter os processadores ocupados a maior parte do tempo possível evitando que alguns deles fiquem ociosos enquanto outros estão executando alguma tarefa. 

Esse balanceamento pode ser estático (o balanceamento ocorre antes da execução de qualquer processo) ou dinâmico (é realizado durante a execução do processo). O principal problema de um balanceamento estático é a dificuldade em estimar com precisão os tempos de execução das várias partes do programa. O modelo de balanceamento dinâmico possui duas classificações:

  \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.5\textwidth]{fig/mestre_escravo.png}
     \caption{Estratégia de balanceamento centralizado mestre/escravo onde um processo controla todas as tarefas e os escravos solicitam e executam as mesmas.} 
     \label{fig:mestre_escravo}
 \end{figure}

\begin{enumerate}
 \item Centralizado (Figura \ref{fig:mestre_escravo})
    \begin{itemize}
      \item Todas as tarefas são manipuladas a partir de uma localização central.
      \item Exemplo: Modelo mestre-escravo - o processo mestre mantém a coleção de tarefas a serem executadas e os processos escravos solicitam tarefas.
    \end{itemize}
 
    \item Não-centralizado  (Figura \ref{fig:pulling})
    \begin{itemize}
      \item Uma coleção de processos trabalhadores opera sobre um problema, e esses trabalhadores interagem entre si, reportando o resultado final a um único processo.
      \item Exemplo: Algoritmo de \textit{polling} aleatório - o processo $P_i$ pede tarefas ao processo $P_x$, onde $x$ é um número selecionado aleatoriamente entre $0$ e $n-1$ (excluindo $i$).
    \end{itemize} 
\end{enumerate}

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.5\textwidth]{fig/pulling.png}
     \caption{Estratégia de balanceamento não-centralizado onde os nós podem se comunicar entre si.} 
     \label{fig:pulling}
 \end{figure}

\subsection{Métricas de Desempenho}\label{Metricas de desempenho}

Ao utilizar uma aplicação paralela, surge o interesse em saber o ganho de velocidade quando comparado a uma aplicação sequencial. Para isso existem algumas métricas utilizadas:

\begin{itemize}
 \item Escalabilidade

 É a propriedade de um sistema que lhe confere a capacidade de aumentar seu desempenho sob uma determinada carga, quando mais recursos (processadores) são acrescentados a esse sistema. Ou seja, pode-se falar que um algoritmo é escalável se ele pode ser utilizado em uma grande quantidade de processadores sem que aconteça uma queda em sua velocidade.
 
 Pode-se dizer que um sistema é escalável quando ele resolve um problema de magnitude $\gamma$ com um recurso $R$, e consegue resolver um problema de magnitude $n\gamma$ com um recurso $nR$. Ou seja, sempre que aumentar os recursos computacionais, aumentará proporcionalmente a capacidade de resolver problemas maiores.
 
 \item \textit{Speed-up}

  Esta métrica mostra quantas vezes um programa paralelo é mais rápido que um serial. Para obter um \textit{speed-up} linear tem-se que obter um programa com tempo de execução $x$ vezes mais rápido quando aumentado em $x$ o número de processadores. Já um \textit{speed-up} super linear seria obter um ganho maior que $x$ quando aumentado em $x$ o número de processadores.
 
 O \textit{speed-up} $S$ para $p$ processadores é calculado pela seguinte formula: $ S(p) = T_s / T_p $, onde $T_s$ é o tempo de execução do programa sequencialmente e $T_p$ é o tempo do programa executando em paralelo para $p$ processadores.
 
 Na prática um \textit{speed-up} linear é difícil de se obter. À medida que a quantidade de processadores aumentam, a comunicação entre os processos aumenta e isso faz o tempo de execução cair, derrubando assim o \textit{speed-up}.
 
\end{itemize}


\section{Estrutura de Dados}\label{Estrutura de dados}

Diversas estruturas de dados que foram criadas na área da computação são muito usadas em problemas de computação gráfica. No contexto desse trabalho, essas estruturas têm o objetivo de fazer uma decomposição espacial do domínio. Com essas decomposições, diversos cálculos são otimizados fazendo uma busca em qual parte da decomposição o objeto de interesse está e limitando os cálculos apenas aos elementos que pertencem a essa decomposição.

Essas estruturas são utilizadas em diversas aplicações como tratamento de colisão e renderização (Figura \ref{fig:ex_decomposicao}). Entre as estruturas de dados bidimensionais, as mais importantes são a \textit{quadtree} e a \textit{binary space partitioning} ou simplesmente BSP.

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.7\textwidth]{fig/ex_decomposicao.jpg}
     \caption{Exemplo de uma decomposição espacial feita para renderização e teste de colisão. Fonte: http://togeskov.net/} 
     \label{fig:ex_decomposicao}
 \end{figure}

\subsection{\textit{Quadtree}}

Uma \textit{quadtree} é uma estrutura de dados baseada em árvore em que cada nó possui exatamente quatro filhos (Figura \ref{fig:quadtree_tree}). Em geral \textit{quadtrees} são utilizadas para decompor domínios bidimensionais em quatro regiões de mesmo tamanho. As \textit{quadtrees} podem ser classificadas de acordo com o tipo do dado que elas representam (regiões, pontos, arestas, polígonos), isso vai depender do tipo de aplicação para o qual ele está sendo utilizada.

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.8\textwidth]{fig/quadtree_tree.png}
     \caption{Uma subdivisão feita por \textit{quadtree} com cinco níveis e sua representação em árvore.} 
     \label{fig:quadtree_tree}
 \end{figure}

\subsection{\textit{Binary Space Partitioning} (BSP)}


BSP (particionamento binário espacial) é um processo genérico que, de forma recursiva, divide um domínio em duas partes, não necessariamente iguais, até que o particionamento do corte satisfaça um ou mais requisitos estabelecidos. Como resultado tem-se dois novos subespaços que podem ainda ser particionados recursivamente. O critério de posicionamento do corte e de parada no particionamento vai depender do objetivo que se deseja ao usar uma BSP. 

Pode-se dizer que a BSP é um caso genérico da \textit{quadtree}. A principal diferença entre elas basicamente é a quantidade de partições criadas (quatro para cada subdivisão na \textit{quadtree} e duas na BSP) e a desvantagem está na hora de encontrar o melhor corte para a BSP, que pode ser bastante custoso se comparado com a \textit{quadtree}.

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.5\textwidth]{fig/ex_BSP.png}
     \caption{Uma subdivisão feita com BSP e sua representação em árvore.} 
     \label{fig:ex_BSP}
 \end{figure}	